package BinaryTree.BinarySearchTree;

import java.util.Stack;

/**
 * 搜索二叉树 左节点小，右节点大
 *
 * @author Liaorun
 */
public class BinarySearchTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int preValue = Integer.MIN_VALUE;

    /**
     * 递归检测是否为搜索二叉树，使用全局变量
     *
     * @param head 头节点
     * @return
     */
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }

        boolean isLeftBST = isBST(head.left);
        if (!isLeftBST) {
            return false;
        }

        // 如果是搜索二叉树，中序遍历，前一个值一定 <= 下一个值
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }

        return isBST(head.right);
    }

    /**
     * 非递归检测是否为搜索二叉树
     *
     * @return
     */
    public static boolean isBST2(Node head) {

        if (head == null) {
            return true;
        }

        int preValue = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<>();

        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();

                if (head.value <= preValue) {
                    return false;
                } else {
                    preValue = head.value;
                }

                head = head.right;
            }
        }

        return true;
    }

    public static class ReturnData {
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    /**
     * 递归检测是否为搜索二叉树，不使用全局变量
     *
     * @param x 头节点
     * @return
     */
    public static ReturnData process(Node x) {
        if (x == null) {
            return null;
        }

        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        boolean isBST = true;
        int min = x.value;
        int max = x.value;

        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }

        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        // 有左节点 && （左子树不是不是搜索二叉树 || 左子节点的值 >= x.value）
        // 因为搜索二叉树左子节点的值 < 当前节点的值
        if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) {
            // 左树不为搜索二叉树，则不为搜索二叉树
            isBST = false;
        }

        // 有右节点 && （右子树不是不是搜索二叉树 || 右子节点的值 >= x.value）
        if (rightData != null && (!rightData.isBST || x.value >= rightData.min)) {
            // 右树不为搜索二叉树，则不为搜索二叉树
            isBST = false;
        }


        return new ReturnData(isBST, min, max);
    }
}
